package pers.vic.basics.leetcode;

import javax.sound.midi.Soundbank;

/**
 * @author Vic.xu
 * @description: 42. 接雨水 {@literal https://leetcode-cn.com/problems/trapping-rain-water/}
 * @date: 2020/12/4 0004 9:24
 */
public class J0042_H_Trap {
    /*
    给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     */

    /**
     * 1. 总体思路:计算每一个列能盛放的雨水
     * 2. 某列左边最高，右边最高，然后取两者中间低的，减去当前 就是当前列能盛放的雨水
     * 3. 如果每次动态的去寻找左右最高 就变成了 O(n^2) 消耗较大
     * 4. 可以转化先分别求每一列[i]的左边最大，右边最大， 这会不会是个动态规划呢？
     * 5. 以求左边做大状态记录为例：
     * 动态规划三步走：
     * 1. 定义dpMaxLeft[i],记录第i列左边做大的值
     * 2. 初始状态 [0] = 0; 可省略
     * 3. 状态转移关系: [i] = max(dpMaxLeft[i-1],[i-1])
     * 6. 右边的最大值求发类似
     */
    public static int trap(int[] height) {
        int sum = 0;
        int len = height.length;
        //第i个元素 记录它左边的最大元素 忽略第0个
        int[] dpMaxLeft = new int[len];
        for (int i = 1; i < len; i++) {
            dpMaxLeft[i] = Math.max(height[i-1], dpMaxLeft[i-1]);
        }
        //第i个元素 记录它左边的最大元素 忽略最后一个       dpMaxRight[len-1] = 0 可忽略
        int[] dpMaxRight = new int[len];
        for (int i = len - 2; i >= 0; i--) {
            dpMaxRight[i] = Math.max(dpMaxRight[i + 1], height[i + 1]);
        }
        //开始求每一列可存盛放的水  忽略 第一和最后一列
        for (int i = 1; i < len - 1; i++) {
            int minSide = Math.min(dpMaxLeft[i], dpMaxRight[i]);
            int cur = height[i];
            sum += minSide > cur ? (minSide - cur) : 0;
        }
        return sum;
    }

    public static void main(String[] args) {

        //6
        System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
        //9
        System.out.println(trap(new int[]{4, 2, 0, 3, 2, 5}));
    }
}
